package com.example.demo.listnode;

import com.example.demo.model.ListNode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 单链表排序
 * https://leetcode.cn/problems/sort-list/description/
 */
public class SortSingleListNode {

    /*public ListNode sortList1(ListNode head) {
        if (head == null) return null;

        int count = 0;
        ListNode tmp = head;
        while (tmp != null) {
            count++;
            tmp = tmp.next;
        }

        ListNode node0 = new ListNode(Integer.MIN_VALUE);
        node0.next = head;

        for (int i = 0; i < count; i++) {
            ListNode pre = node0;
            while (i > 0) {
                pre = pre.next;
                i--;
            }
            ListNode cur = pre.next;

            while (cur != null && cur.next != null) {
                if (cur.val > cur.next.val) {
                    ListNode curNext = cur.next;
                    cur.next = cur.next.next;
                    curNext.next = cur;
                    pre.next = curNext;
                }
                pre = pre.next;
                cur = pre.next;
            }
        }

        return node0.next;
    }*/

    public ListNode sortList2(ListNode head) {
        if (head == null) return null;

        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }

        list.sort(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });

        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).next = list.get(i + 1);
        }

        list.get(list.size() - 1).next = null;
        return list.get(0);
    }

    public ListNode sortList3(ListNode head) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));

        while (head != null) {
            heap.offer(head);
            head = head.next;
        }

        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        while (heap.size() > 0) {
            cur.next = heap.peek();
            heap.poll();
            cur = cur.next;
        }
        cur.next = null;
        return dummy.next;
    }
}
